package com.leetcode.partition7;

import com.leetcode.common.TreeNode;

import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/8/5 10:50
 */
public class LC662二叉树最大宽度 {

    @SuppressWarnings("ConstantConditions")
    public static int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        //bfs建立索引树
        LinkedList<TreeNode> treeNodeQueue = new LinkedList<>();
        LinkedList<Integer> indexQueue = new LinkedList<>();
        int result = 0;
        treeNodeQueue.add(root);
        indexQueue.add(1);

        while (!treeNodeQueue.isEmpty()) {
            int levelSize = treeNodeQueue.size();
            //取出当前层，当前层的宽度=当前层最后一个节点的索引-当前层第一个节点的索引+1
            int firstIndex = indexQueue.peek();
            int currentIndex = firstIndex;
            while (levelSize-- > 0) {
                TreeNode current = treeNodeQueue.poll();
                currentIndex = indexQueue.poll();
                if (current.left != null) {
                    treeNodeQueue.add(current.left);
                    indexQueue.add(currentIndex * 2);
                }
                if (current.right != null) {
                    treeNodeQueue.add(current.right);
                    indexQueue.add(currentIndex * 2 + 1);
                }
            }
            result = Math.max(result, currentIndex - firstIndex + 1);
        }
        return result;
    }

    public static void main(String[] args) {

    }
}
